The present invention relates to a method and/or architecture for carry chains generally and, more particularly, to a method and/or architecture for implementing a reduced product term carry chain and adder.
A programmable logic device (PLD) provides an economical and efficient means for implementing predetermined Boolean logic functions in an integrated circuit. Such a device consists of, generally, an AND plane configured to generate predetermined product terms in response to a plurality of inputs, a group of fixed/programmable OR gates configured to generate a plurality of sum-of-products (SOP) terms in response to the product terms, and a number of logic elements (i.e., macrocells) configured to generate a desired output in response to the sum-of-products terms. The sum-of-products terms can also be generated using programmable NOR-NOR logic or programmable NAND-NAND logic.
One of the main disadvantages of complex programmable logic devices (CPLDs) and other programmable logic devices (PLDs) that do not contain dedicated carry chain circuitry is the size and performance of the arithmetic function implementations. Arithmetic function implementations in CPLDs can be optimized for area and/or speed. These optimizations, however, are based only on optimizing the topology of the implementation. Without dedicated carry chain circuitry, arithmetic function implementations that are optimized for speed require a large amount of device resources. The required resources can grow to become a significant portion of the targeted device, thereby limiting the amount of resources for other portions of the design. Conversely, implementations that are optimized for area require fewer device resources, but are typically much slower than those optimized for speed. The coarse-grain nature of the CPLD does not allow for a good speed/area tradeoff when implementing arithmetic functions.
Referring to FIG. 1, a block diagram of a PLD 10 containing dedicated carry chain circuitry is shown. The PLD 10 has an AND (product term) array 12, a product term matrix (PTM) 14, and a macrocell 16. The AND plane 12 generates carry product term signals CPT0 and CPT1. The carry product terms are presented to the PTM 14 and the macrocell 16. The PTM 14 includes a fixed 16-input OR gate 18. The OR gate 18 generates a sum of products term signal OR_IN that is presented to the macrocell 16.
The macrocell 16 comprises a multiplexer 20, an AND gate 22, a multiplexer 24, an XOR gate 26, a register 28, and a multiplexer 30. The multiplexer 20 has a non-inverting input that receives the signal CPT0, an inverting input that receives the signal CPT1, a control input that receives a control signal from the AND gate 22, and an output that presents the signal Ci to a first input of the multiplexer 24 and to an output of the macrocell 16. The AND gate 22 generates the control signal in response to a carry in signal Cixe2x88x921 and a configuration bit C2.
The multiplexer 24 has a second input that is connected to a supply voltage VCC, a third input that is connected to a Q output of the register 28, and a fourth input that is connected to a supply voltage ground VSS. The multiplexer 24 selects one of the input signals for presentation to a first input of the XOR gate 26 in response to a pair of configuration bits C0 and C1.
The XOR gate 26 has a second input that receives the signal OR_IN and an output that presents a signal to a D input of the register 28 and a first input of the multiplexer 30. The multiplexer 30 can select either the output of the XOR gate 26 or the Q output of the register 28 for presentation as an output signal OUT in response to a configuration bit Cx.
Referring to FIG. 2, a block diagram illustrating a 4-bit ripple carry adder 32 implementing the macrocell structure of FIG. 1 is shown. The ripple carry adder 32 generates output sum bits S0-S3 in response to sum operand input bits A0-A3 and B0-B3. The 4-bit ripple carry full adder includes 4 macrocells 16a-16d. Each of the macrocells 16a-16d is similar to the macrocell 16 of FIG. 1. However, the register 28 and the multiplexer 30 have not been included in any of the macrocells in FIG. 2 for clarity. For the purposes of FIG. 2, it is assumed that the configuration bit Cx is set to select the output of the gate 26 and to bypass the register 28. A description of the operation of a ripple carry adder may be found in U.S. Pat. No. 6,034,546, which is hereby incorporated by reference in its entirety.
For the first sum operand bits A0 and B0, the first configuration bit C20 is set to 0, so as to cause the multiplexer 20a to always select the signal CPT00, that is set to CIN0, the initial carry into the sum. Since the signal CPT00 is always selected by the multiplexer 20a, CPT10 is not used. The signal OR_IN0 is set to the result of the XOR operation A0⊕B0. Configuration bits C00 and C10 are set to 1 and 0, respectively, so that the multiplexer 24a presents the signal CIN0 to a first input of the gate 26a. The gate 26a performs the XOR operation OR_IN0⊕CIN0 and presents the result as the least significant sum bit S0.
The output of the multiplexer 20a (i.e., CIN0) is propagated to the select line of the multiplexer 20b, as C21 is set to 1, causing the output of the gate 22b to follow the output of the multiplexer 20a. To generate the signal CIN1 (i.e., the carry input for sum bit S1) the signal CPT01 is set to A0*B0 and the signal CPT11 is set to /A0*/B0. The multiplexer 20b, therefore, outputs the carry-in signal CIN1 for sum bit S1. The multiplexer 24b is configured to present the signal CIN1 to an input of the gate 26b. Thereafter, the gate 26b presents the sum bit S1, the result of the logical XOR operation on OR_IN1 and CIN1. Sum bits S2 and S3 are obtained in a similar manner.
Each macrocell 16a-16d requires 4 product terms to implement a 1-bit ripple carry adder. Two dedicated carry product terms are used to generate the carry input Ci (i.e., Aixe2x88x921*Bixe2x88x921 and /Aixe2x88x921*/Bixe2x88x921). Two general purpose product terms are needed to generate the XOR, (Ai⊕Bi), one for Ai*/Bi and one for /Ai*Bi. The second two product terms are implemented in the AND-OR plane of the PLD 10.
The macrocell 16 has a disadvantage of requiring 4 product terms per macrocell to implement a ripple carry adder. Product terms can require a large number of transistors to implement. For example, a PLD with 39 inputs can require 78 to 156 or more transistors per product term. Reducing the number of product terms required to implement a carry chain can reduce the number of transistors required and reduce the die size of a PLD. However, the structure of the macrocell 16 limits the amount of reduction possible.
An architecture and/or method for implementing a carry chain with two product terms per macrocell that can implement a ripple carry adder would be desirable.
The present invention concerns a programmable logic device comprising one or more macrocells and a product term array. The macrocells may comprise logic that may be configured to (i) generate and propagate a carry signal and (ii) generate a sum bit. The product term array may comprise two product terms per macrocell.
The objects, features and advantages of the present invention include providing a method and/or architecture for implementing a reduced product term carry chain that may (i) be implemented in a complex programmable logic device (CPLD), (ii) require fewer transistors, (iii) reduce die size, and/or (iv) implement an n-bit ripple carry adder with two product terms per macrocell.